package lee.study.Data_Struct.ClassCompare;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class MyComparator implements Comparator<Integer> {//实现小堆转大堆的比较器接口

    @Override
    public int compare(Integer o1, Integer o2) {//重写比较器中的compare方法
        return o2 - o1;//如果是return o1 - o2 那么返回的就是一个小堆
    }
}

public class TopK {
    public static Integer[] topK(int[] array, int k) {

        MyComparator myComparator = new MyComparator();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(myComparator);
        //实现了myComparator比较器，此时的maxHeap是一个大堆

        for (int i = 0; i < array.length; i++) {
            if (maxHeap.size() < k) {//放入前k个元素
                maxHeap.offer(array[i]);
            }
            else {
                Integer val = maxHeap.peek();
                //后面的元素与堆顶元素比较
                if (val != null && val > array[i]) {//小于堆顶元素，放进来
                    maxHeap.poll();
                    maxHeap.offer(array[i]);
                }
            }
        }
        Integer[] ret = new Integer[k];//ret用来接收maxHeap的内容并返回
        for (int i = 0; i < k; i++) {
            int tmp = maxHeap.poll();
            ret[i] = tmp;
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] array = {1, 6, 3, 8, 12, 53, 86, 213, 65, 22, 54, 15, 63};
        Integer[] array1 = topK(array, 4);
        System.out.println(Arrays.toString(array1));
    }
}
